using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using GeoAzure.Core.Threading;
using ProtoBuf;

namespace GeoAzure.Core
{
    [Serializable]
    public class TreeNode<T> : ITreeNodeParent<T>
        where T : class
    {
        #region Mutable state variables

        private readonly List<IndexEntry<T>> _entries;
        internal List<IndexEntry<T>> Entries
        {
            get
            {
                //var lockState = _nodeLock.LockState;
                //Debug.Assert(lockState == OneManyLockState.OwnedByReaders || lockState == OneManyLockState.OwnedByWriter || lockState == OneManyLockState.OwnedByReadersAndWriterPending, "Attempt to read entries in a node without locking it.");
                Debug.Assert(_nodeLock.IsReadLockHeld | _nodeLock.IsWriteLockHeld, "Attempt to read entries in a node without locking it.");
                return _entries;
            }
        }

        private GeoRectangle _bounds;
        public GeoRectangle Bounds
        {
            get
            {
                Debug.Assert(_nodeLock.IsReadLockHeld | _nodeLock.IsWriteLockHeld, "Attempt to read bounds in a node without locking it.");
                return _bounds;
            }
        }

        //internal ITreeNodeParent<T> Parent { get; set; }

        private TreeNode<T> LeftSibling { get; set; }

        private TreeNode<T> _rightSibling;
        internal TreeNode<T> RightSibling
        {
            get
            {
                Debug.Assert(_nodeLock.IsReadLockHeld | _nodeLock.IsWriteLockHeld, "Attempt to read right sibling in a node without locking it.");
                return _rightSibling;
            }
            private set { _rightSibling = value; }
        }

        private long _lsn;
        /// <summary>
        /// The Logical Sequence Number of this node.
        /// </summary>
        internal long Lsn
        {
            get
            {
                Debug.Assert(_nodeLock.IsReadLockHeld | _nodeLock.IsWriteLockHeld, "Attempt to read LSN in a node without locking it.");
                return _lsn;
            }
            private set { _lsn = value; }
        }

        #endregion

        [ProtoMember(2)]
        private readonly int _level;

        [NonSerialized]
        //private readonly OneManyLock _nodeLock = new OneManyLock();
        private readonly ReaderWriterLockSlim _nodeLock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);

        #region Construction

        internal TreeNode(int level, long nodeLsn)
            : this(
                level, null, null, new List<IndexEntry<T>>(OverflowAlgorithm<T>.MaxObjectsPerNode + 1), GeoRectangle.NullRectangle, nodeLsn)
        {
        }

        private TreeNode(int level, TreeNode<T> leftSibling, TreeNode<T> rightSibling, List<IndexEntry<T>> entries, GeoRectangle bounds, long nodeLsn)
        {
            //Parent = level;
            LeftSibling = leftSibling;
            _rightSibling = rightSibling;
            _level = level;
            _entries = entries;
            _bounds = bounds;
            //AssignParentToElements();
            _lsn = nodeLsn;
        }

        /// <summary>
        /// Default constructor used by deserialization
        /// </summary>
        private TreeNode()
        {
        }

        [ProtoAfterDeserialization]
        private void AfterDeserialization()
        {
            //if (IsLeaf)
            //    return;
            //for (int i = 0; i < _entries.Count; i++)
            //{
            //    _entries[i].Node.Parent = this;
            //}
        }

        #endregion

        private void AssignParentToElements()
        {
            // leaf nodes do not contain nodes, so no parent to assign
            //if (IsLeaf)
            //    return;
            //foreach (IndexEntry<T> entry in Entries)
            //{
            //    entry.Node.Parent = this;
            //}
        }

        #region ITreeNodeParent implementation

        public void Insert(InsertionContext<T> context)
        {
            //if (context.TargetLevel == Level)
            //    AddChild(context);
            //else
            //{
            //    TreeNode<T> insertionNode = ChooseInsertionSubtree(context.Entry);
            //    insertionNode.Insert(context);
            //}
        }

        public bool Delete(DeletionContext<T> context)
        {
            //if (Level == context.TargetLevel)
            //{
            //    // just remove the element from our element list
            //    // TODO: implement deletion algorithm
            //    IndexEntry<T> entryForItem = _entries.Find(e => e == context.Entry);
            //    if (_entries.Remove(entryForItem))
            //    {
            //        // update our linked list of nodes
            //        // note that this update is needed, even if the contrary is stated in the algorithm paper
            //        // indeed, the removed node will never be garbage-collected if there are still references to it
            //        // in its former siblings
            //        // TODO: TreeNode contains disposable locks, and thus must be disposed of when no longer needed
            //        if (!IsLeaf)
            //        {
            //            var removedNode = context.Entry.Node;
            //            var r = removedNode.RightSibling;
            //            var l = removedNode.LeftSibling;
            //            if (l != null)
            //                l.RightSibling = r;
            //            if (r != null)
            //                r.LeftSibling = l;
            //        }
            //        // and initiate tree packing
            //        // check if this node is underfilled and will be deleted
            //        if (!Inserter.Overflow.HandleNodeUnderflow(this, context))
            //            // if no deletion will occur, then readjust our bounds
            //            ReadjustBounds();
            //        return true;
            //    }
            //}
            //else
            //{
            //    Debug.Assert(!IsLeaf); // we should never reach here for leaf nodes. That means level is erroneous
            //    foreach (IndexEntry<T> childEntry in Entries)
            //    {
            //        if (childEntry.Bounds.Contains(context.Entry.Bounds))
            //            if ((childEntry.Node).Delete(context))
            //                return true;
            //    }
            //}
            return false;
        }

        public int Level
        {
            get { return _level; }
        }

        #endregion

        public bool IsLeaf
        {
            get { return _level == 0; }
        }

        internal TreeNode<T> SplitNode(List<IndexEntry<T>> newNodeEntryList, GeoRectangle newNodeBounds, GeoRectangle updatedBounds, InsertionContext<T> context)
        {
            //Debug.Assert(_nodeLock.LockState == OneManyLockState.OwnedByWriter, "Attempt to split a node that is not write-locked.");
            Debug.Assert(_nodeLock.IsWriteLockHeld, "Attempt to split a node that is not write-locked.");
            // we propagate our LSN to our new sibling
            // TODO: how to make this method thread-safe?
            var siblingNode = new TreeNode<T>(Level, this, RightSibling, newNodeEntryList, newNodeBounds, Lsn);
            if (RightSibling != null)
                RightSibling.LeftSibling = siblingNode;
            RightSibling = siblingNode;
            _bounds = updatedBounds;
            // we update our LSN after a split
            Lsn = context.TargetIndex.GetNewLsn();
            // we place a read lock on the new node, to allow creating an entry for it later
            siblingNode.LockForReading();
            return siblingNode;
        }

        /// <summary>
        /// Adds an <see cref="IndexEntry{T}"/> to this node instance.
        /// The <see cref="Bounds"/> of the node are readjusted if necessary.
        /// </summary>
        /// <param name="entry">.The entry to add</param>
        /// <returns>true if the <see cref="Bounds"/> were updated, false if they did not change.</returns>
        internal bool AddEntry(IndexEntry<T> entry)
        {
            Debug.Assert(_nodeLock.IsWriteLockHeld, "Attempt to add an entry to a node that is not write-locked.");
            Entries.Add(entry);
            if (Entries.Count == 1)
            {
                _bounds = entry.Bounds;
                return true;
            }
            
            var previousBounds = _bounds;
            _bounds = _bounds.EnsureContainsRectangle(entry.Bounds);
            return previousBounds != _bounds;
        }

        private void AddChild(InsertionContext<T> context)
        {
            //long nodeLsn = 0;
            //if (!IsLeaf)
            //{
            //    var node = context.Entry.Node;
            //    Debug.Assert(node != null);
            //    node.Parent = this;
            //    nodeLsn = node.Lsn;
            //}

            //Entries.Add(context.Entry);
            //if (Entries.Count == 1)
            //    Bounds = context.Entry.Bounds;
            //else
            //{
            //    // inflate bounds
            //    //ReadjustBounds();
            //    //Bounds = Bounds.EnsureContainsRectangle(context.element.Bounds);
            //    //Inserter.Overflow.HandleNodeOverflow(this, context);
            //}
        }

        public bool IsRoot
        {
            get
            {
                return false;
                //return GetType() != Parent.GetType();
                // if we are root then our parent is the index itself, not a tree node
            }
        }

        [Conditional("DEBUG")]
        public void AssertNodeIsValid(bool amITheRootNode, bool recursive)
        {
            //Debug.Assert(_nodeLock.LockState == OneManyLockState.Free, "Node is still locked!");
            Debug.Assert(!_nodeLock.IsReadLockHeld && !_nodeLock.IsWriteLockHeld, "Node is still locked!");
            var bounds = _bounds;
            if (!amITheRootNode)
                Debug.Assert(_entries.Count >= OverflowAlgorithm<T>.MinObjectsPerNode &&
                             _entries.Count <= OverflowAlgorithm<T>.MaxObjectsPerNode);
            else
            {
                int[] nodeCounts = new int[Level + 1];
                CountNodes(nodeCounts);
                CheckLinkChain(nodeCounts, recursive);
            }
            foreach (var entry in _entries)
            {
                Debug.Assert(bounds.Contains(entry.Bounds),
                             "The bounds of the node do not contain the bounds of at least one of its entries.");
                if (!IsLeaf)
                {
                    var childNode = entry.Node;
                    Debug.Assert(childNode != null);
                    Debug.Assert(childNode.Level == Level - 1);
                    //Debug.Assert(childNode.Parent == this);
                    if (recursive)
                        childNode.AssertNodeIsValid(false, true);
                }
            }
        }

        [Conditional("DEBUG")]
        public void CheckLinkChain(int[] expectedNodeCounts, bool recursive)
        {
            if (IsLeaf)
                return;
            var firstChild = _entries[0].Node;
            TreeNode<T> current = firstChild;
            int chainLength = 1;
            while ((current = current.LeftSibling) != null)
            {
                chainLength++;
            }
            current = firstChild;
            while ((current = current._rightSibling) != null)
            {
                chainLength++;
            }
            Debug.Assert(chainLength == expectedNodeCounts[Level - 1], "Link chain is incorrect", "Chain length: {0} expected length {1} #child nodes {2}", chainLength, expectedNodeCounts[Level - 1], _entries.Count);
            if (recursive)
                firstChild.CheckLinkChain(expectedNodeCounts, true);
        }

        internal void CountElementsInLeaves(ref int result)
        {
            if (IsLeaf)
                result += _entries.Count;
            else
            {
                foreach (IndexEntry<T> entry in _entries)
                {
                    entry.Node.CountElementsInLeaves(ref result);
                }
            }
        }

        internal void CountNodes(int[] results)
        {
            if (IsLeaf)
                return;
            results[Level - 1] += _entries.Count;
            foreach (IndexEntry<T> entry in _entries)
            {
                entry.Node.CountNodes(results);
            }
        }

        internal void LockForReading()
        {
            //_nodeLock.Enter(false);
            _nodeLock.EnterReadLock();
        }

        internal void ReleaseReadLock()
        {
            //_nodeLock.Leave(false);
            _nodeLock.ExitReadLock();
        }

        internal void LockForWriting()
        {
            //_nodeLock.Enter(true);
            _nodeLock.EnterWriteLock();
        }

        internal void ReleaseWriteLock()
        {
            //_nodeLock.Leave(true);
            _nodeLock.ExitWriteLock();
        }

        public void ReadjustBounds()
        {
            //GeoRectangle currentBounds = Bounds;
            //GeoRectangle adjustedBounds = GeoRectangle.CreateMinimumBoundingRectangle(Entries);
            //if (!adjustedBounds.Equals(currentBounds))
            //{
            //    Bounds = adjustedBounds;
            //}
        }

        internal bool UpdateEntry(IndexEntry<T> entryToUpdate)
        {
            //Debug.Assert(_nodeLock.LockState == OneManyLockState.OwnedByWriter, "Attempt to modify an entry in a node that is not write-locked.");
            Debug.Assert(_nodeLock.IsWriteLockHeld, "Attempt to modify an entry in a node that is not write-locked.");
            Debug.Assert(Entries.Contains(entryToUpdate), "A TreeNode was asked to update an entry it does not own.");

            bool entryBoundsUpdated = entryToUpdate.Update();

            if (entryBoundsUpdated)
            {
                var previousBounds = _bounds;
                _bounds = _bounds.EnsureContainsRectangle(entryToUpdate.Bounds);
                return previousBounds != _bounds;
            }
            return false;
        }
    }
}